Sau khi bị trục xuất khỏi quân ngũ vào ngày 30 tháng 5,[23] thì ngay hôm sau đó[23] hoặc hôm tiếp nữa là ngày 1 tháng 6, Heydrich đã xin gia nhập Đảng Quốc xã ở Hamburg.[24][25] Sáu tuần sau, vào ngày 14 tháng 7, ông chính thức gia nhập lực lượng SS.[26] Số thứ tự đảng của ông là 544.916, còn số thứ tự SS của ông là 10.120.[27] Những người gia nhập Đảng Quốc Xã sau khi Hitler lên nắm quyền vào tháng 1 năm 1933 đều phải đối mặt với những nghi ngờ từ Alte Kämpfer (cựu chiến hữu, tên gọi để chỉ những đảng viên gia nhập đảng sớm nhất). Họ bị nghi ngờ vì chỉ gia nhập đảng với mục đích thăng tiến dễ dàng hơn là vì tin tưởng vào cương lĩnh của đảng cũng như chương trình Xã hội Chủ nghĩa Quốc gia. Ngày vào đảng năm 1931 của Heydrich đủ sớm để dập tắt sự nghi ngờ rằng ông gia nhập chỉ để mưu đồ thăng tiến, nhưng không đủ sớm để được coi là một Alte Kämpfer.[24]

Năm 1931, Heinrich Himmler bắt đầu thành lập một bộ phận phản gián của SS. Theo lời khuyên của cộng sự tên là Karl von Eberstein, người bạn của Lina, Himmler đã đồng ý phỏng vấn Heydrich, nhưng đã hủy cuộc hẹn vào phút cuối.[28] Tuy nhiên, Lina bỏ qua tin nhắn này và vẫn đóng gói vali cho Heydrich và gửi ông đến München. Eberstein đã gặp Heydrich tại nhà ga và đưa ông đến gặp Himmler.[28] Himmler yêu cầu Heydrich truyền đạt ý tưởng của mình để phát triển ban tình báo cho SS. Himmler rất ấn tượng tới nỗi ông ta đã nhận Heydrich vào làm việc ngay lập tức.[29][30]

Mặc dù mức lương khởi điểm hàng tháng là 180 Reichsmark (tương đương € 576 theo tỷ giá năm 2009) khá thấp, nhưng Heydrich vẫn quyết định nhận công việc này vì gia đình của Lina ủng hộ phong trào Đức quốc xã và tính chất cách mạng và quân sự của chức vụ này đã lôi cuốn ông.[31] Lúc đầu, ông ta phải chia sẻ một văn phòng và máy đánh chữ với một đồng nghiệp, nhưng đến năm 1932 Heydrich đã kiếm được 290 Reichsmark mỗi tháng (tương đương € 1.009 theo tỷ giá năm 2009), một mức lương mà ông mô tả là "thoải mái".[32] Khi quyền lực và tầm ảnh hưởng của ông tăng lên trong suốt những năm 1930, sự giàu có của ông cũng đã tăng lên một cách tương xứng; vào năm 1935, ông nhận được mức lương cơ bản là 8.400 Reichsmark (tương đương € 32.854 năm 2009) và khoản trợ cấp 12.000 Reichsmark (tương đương € 46.934 năm 2009) và đến năm 1938, thu nhập hàng năm của ông đã tăng lên 17.371 Reichsmark (tương đương € 65.749 trong năm 2009).[33] Heydrich sau đó đã nhận được Nhẫn Đầu Lâu từ Himmler để khen thưởng cho những đóng góp trong quân phục SS của ông.[34]

Vào ngày 1 tháng 8 năm 1931, Heydrich bắt đầu công việc của mình với tư cách là giám đốc của 'Ban Ic' mới (ban tình báo).[30] Ông thành lập văn phòng tại Nhà Nâu, trụ sở của Đảng Quốc xã ở München. Đến tháng 10 năm đó, ông đã tạo ra một mạng lưới gián điệp và người cung cấp thông tin cho mục đích thu thập thông tin tình báo. Những thông tin thu thập được sẽ được sử dụng cho mục đích hăm dọa phục vụ cho mục đích chính trị.[35] Thông tin về hàng ngàn người đã được ghi lại trên thẻ chỉ mục và được lưu trữ tại Nhà Nâu.[36] Để đánh dấu dịp đám cưới của Heydrich vào tháng 12, Himmler đã thăng cấp ông lên cấp bậc SS-Sturmbannführer (tương đương thiếu tá).[37]

Năm 1932, kẻ thù của Heydrich đã lan truyền tin đồn về việc ông có tổ tiên được cho là người Do Thái.[38] Wilhelm Canaris cho biết rằng ông ta đã thu thập được những bản sao chứng minh Heydrich có tổ tiên Do Thái, tuy nhiên những bản sao chép này không bao giờ lộ ra.[39] Gauleiter Rudolf Jordan từng tuyên bố rằng Heydrich không phải là người Aryan thuần chủng.[38] Trong các tổ chức Quốc xã thì những lời nói bóng gió như vậy có thể gây tổn hại, ngay cả đối với người đứng đầu ban phản gián của Reich như Heydrich. Gregor Strasser đã chuyển các cáo buộc sang chuyên gia chủng tộc của Đảng Quốc xã, Achim Gercke, để điều tra gia phả của Heydrich.[38] Gercke báo cáo rằng Heydrich là "... có nguồn gốc từ Đức và không có bất kỳ dòng máu Do Thái và da màu nào".[40] Ông nhấn mạnh rằng những tin đồn kia là hoàn toàn vô căn cứ. Mặc dù vậy, Heydrich đã gặp riêng thành viên SD là Ernst Hoffmann để yêu cầu tiếp tục điều tra nhằm xua tan những tin đồn.[38]

Tổng hành dinh của Gestapo tại Prinz-Albrecht-Strasse ở Berlin, 1933

Gestapo và SD

Vào giữa năm 1932, Himmler đã bổ nhiệm Heydrich thành giám đốc của cơ quan an ninh vừa mới được đổi tên thành Sicherheitsdienst (SD).[30] Dịch vụ phản gián của Heydrich đã phát triển thành một cỗ máy khủng bố và đe dọa hiệu quả. Với việc Hitler phấn đấu giành quyền lực tuyệt đối ở Đức, Himmler và Heydrich mong muốn kiểm soát lực lượng cảnh sát chính trị của tất cả 17 bang của Đức. Họ bắt đầu với Bayern. Năm 1933, Heydrich tập hợp một số người của mình từ SD và cùng nhau họ xông vào trụ sở cảnh sát ở München và chiếm quyền tiếp quản tổ chức bằng các chiến thuật đe dọa. Himmler trở thành cảnh sát trưởng München còn Heydrich trở thành chỉ huy của Cục IV, Cảnh sát chính trị.[41]

Năm 1933, Hitler trở thành Thủ tướng Đức, và thông qua một loạt các sắc lệnh,[42] Hitler đã trở thành Führer kiêm Reichskanzler (Quốc trưởng kiêm thủ tướng) của Đức.[43] Các trại tập trung đầu tiên, ban đầu được dự định là nơi giam giữ các đối thủ chính trị, đã được thành lập vào đầu năm 1933. Đến cuối năm đó, đã có hơn năm mươi trại như thế được thành lập.[44]

Hermann Göring thành lập Gestapo vào năm 1933 với tư cách là một lực lượng cảnh sát Phổ. Khi Göring chuyển toàn quyền đối với Gestapo sang Himmler vào tháng 4 năm 1934, nó ngay lập tức trở thành một công cụ khủng bố dưới sự giám sát của SS.[45] Himmler phong Heydrich làm người đứng đầu Gestapo vào ngày 22 tháng 4 năm 1934.[46] Vào ngày 9 tháng 6 năm 1934, Rudolf Hess tuyên bố SD là cơ quan tình báo chính thức của Đức Quốc xã.[47]

SS-Brigadeführer (thiếu tướng) Heydrich, chỉ huy lực lượng cảnh sát Bayern và lực lượng SD, ảnh chụp tại München, 1934

Tiêu diệt lực lượng SA

Vào tháng 4 năm 1934, theo yêu cầu của Hitler, Heydrich và Himmler bắt đầu xây dựng một hồ sơ về nhà lãnh đạo Sturmabteilung (SA) là Ernst Röhm trong nỗ lực loại bỏ ông ta do Hitler nghi ngại Ernst Röhm sẽ là một mối đe dọa có thể tranh quyền lãnh đạo đảng với mình. Vào thời điểm này, SS vẫn là một phần trực thuộc SA, tổ chức bán quân sự đầu tiên của Đức Quốc xã hiện có số lượng hơn 3 triệu thành viên.[48] Theo chỉ đạo từ Hitler, Heydrich, Himmler, Göring và Viktor Lutze đã lập danh sách những người nên bị loại bỏ, bắt đầu với bảy quan chức SA hàng đầu và bao gồm nhiều quan chức khác. Vào ngày 30 tháng 6 năm 1934, SS và Gestapo đã hành động trong các vụ bắt giữ hàng loạt phối hợp kéo dài trong hai ngày. Röhm cùng với các chỉ huy của SA bị bắn mà không thông qua xét xử.[49] Cuộc thanh trừng được gọi với cái tên Đêm của những con dao dài. Trong cuộc thanh trừng đẫm máu này, có tới 200 người đã phải bỏ mạng. Lutze được bổ nhiệm làm người đứng đầu mới của SA và nó đã được chuyển đổi thành một hội thể thao, thể dục.[50]

Heydrich và các sĩ quan SS khác cùng vợ của họ năm 1937

Sau khi loại bỏ được SA, Heydrich bắt đầu xây dựng Gestapo thành một công cụ thi hành tội ác khét tiếng. Ông đã cải thiện hệ thống thẻ chỉ mục, phân chia các loại người phạm tội bằng các thẻ được mã hóa màu.[51] Gestapo có thẩm quyền bắt giữ công dân mà họ nghi ngờ, còn định nghĩa về tội phạm là do họ tự quyết. Luật Gestapo được thông qua vào năm 1936 đã trao cho cảnh sát quyền hành động ngoài pháp lý. Điều này dẫn đến việc thi hành một cách vô tội vạ quyền "giam giữ phòng ngừa" (Schutzhaft), một uyển ngữ cho quyền giam cầm người dân mà không cần tố tụng pháp lý. Đối với các đối tượng này, Tòa án không được phép điều tra hoặc can thiệp.[52] Gestapo được coi là hành động hợp pháp miễn là những gì họ làm thể hiện ý chí lãnh đạo. Mọi người bị bắt giữ một cách tùy tiện, bị đưa đến các trại tập trung hoặc bị giết.[44]

Himmler bắt đầu phát triển khái niệm về một tôn giáo German và muốn các thành viên SS rời khỏi Giáo hội. Đầu năm 1936, Heydrich rời khỏi Giáo hội Công giáo. Vợ ông, Lina cũng đã làm như vậy một năm trước. Heydrich không chỉ cảm thấy mình không còn có thể làm thành viên, mà còn lo ngại sức ảnh hưởng và quyền lực chính trị của Giáo hội là một mối nguy hiểm cho nhà nước Quốc Xã.[53]

Hợp nhất lực lượng cảnh sát

Vào ngày 17 tháng 6 năm 1936, tất cả các lực lượng cảnh sát trên khắp nước Đức đã được hợp nhất, sau khi Hitler bổ nhiệm Himmler làm Chỉ huy lực lượng Cảnh sát Đức. Với sự bổ nhiệm này của Hitler, Himmler và phó của ông, Heydrich, đã trở thành hai trong số những người đàn ông quyền lực nhất trong chính quyền nội bộ của Đức.[54] Himmler ngay lập tức tổ chức lại cảnh sát thành hai nhóm: Ordnungspolizei (Cảnh sát trật tự; Orpo), bao gồm cả cảnh sát mặc đồng phục quốc gia và cảnh sát thành phố, và Sicherheitspolizei (Cảnh sát an ninh; SiPo), bao gồm Geheime Staatspolizei (Mật vụ; Gestapo) và Kriminalpolizei (Cảnh sát hình sự; Kripo).[55] Vào thời điểm đó, Heydrich là người đứng đầu SiPo và SD. Heinrich Müller là giám đốc hoạt động của Gestapo.[56]

Heydrich được giao nhiệm vụ giúp tổ chức Thế vận hội Mùa hè 1936 tại Berlin. Nhiều nội dung thi đấu đã được sử dụng để thúc đẩy các mục tiêu tuyên truyền của chế độ Đức Quốc Xã. Đại sứ thiện chí đã được gửi đến các quốc gia đang xem xét tẩy chay. Bạo lực chống Do Thái đã bị cấm trong thời gian này, và các quầy tin tức được yêu cầu ngừng hiển thị các bản sao của tờ Der Stürmer.[57][58] Đối với những đóng góp của mình trong sự thành công của Thế Vận Hội lần này, Heydrich đã được trao tặng Deutsches Olympiaehrenzeichen tức Huân chương Thế vận hội Olympic Đức (Hạng nhất).[34]

Arthur Seyss-Inquart, Adolf Hitler, Heinrich Himmler, và Heydrich tại Viên, tháng 3 1938

Vào tháng 1 năm 1937, Heydrich đã chỉ đạo SD bắt đầu bí mật thu thập và phân tích dư luận và báo cáo lại những điều mà họ thu thập được.[59] Sau đó, ông đã nhờ Gestapo thực hiện các cuộc khám xét nhà cửa, bắt giữ và thẩm vấn, và do đó đã hoàn toàn hoàn tất việc kiểm soát dư luận.[60] Vào tháng 2 năm 1938 khi Thủ tướng Áo Kurt Schuschnigg chống lại đề xuất sáp nhập Áo vào Đức của Hitler, Heydrich đã tăng cường áp lực đối với Áo bằng cách tổ chức các cuộc biểu tình của Đức Quốc xã và tuyên truyền tuyên truyền tại Viên nhấn mạnh dòng máu Đức chung của hai nước.[61] Trong sự kiên Anschluss vào ngày 12 tháng 3, Hitler tuyên bố hợp nhất Áo với Đức Quốc Xã.[62]

Vào giữa năm 1939, Heydrich đã thành lập Quỹ Stiftung Nordhav để lấy chiếm đoạt bất động sản cho SS và Cảnh sát an ninh sử dụng làm nhà khách và điểm nghỉ mát.[63] Biệt thự Wannsee, mà Stiftung Nordhav mua lại vào tháng 11 năm 1940,[64] là nơi diễn ra Hội nghị Wannsee (20 tháng 1 năm 1942). Heydrich là diễn giả chính với sự hỗ trợ từ Adolf Eichmann.[39] Tại Wannsee, các quan chức cấp cao của Đức Quốc xã đã chính thức lên kế hoạch trục xuất và tiêu diệt tất cả người Do Thái trên lãnh thổ do Đức chiếm đóng và tại những quốc gia chưa bị chinh phục.[65] Hành động này đã được phối hợp giữa các đại diện từ các cơ quan nhà nước Đức Quốc xã có mặt tại cuộc họp.[66]

Vào ngày 27 tháng 9 năm 1939, SD và SiPo (được tạo thành từ Gestapo và Kripo) đã được tái tổ chức thànhReichssicherheitshauptamt (RSHA), được đặt dưới sự kiểm soát của Heydrich.[67] Heydrich nhậm chức Chef der Sicherheitspolizei und des SD (Chỉ huy lực lượng Cảnh sát an ninh và SD) hoặc CSSD vào ngày 1 tháng 10.[68] Heydrich trở thành chủ tịch của Ủy ban cảnh sát hình sự quốc tế (sau này gọi là Interpol) vào ngày 24 tháng 8 năm 1940 và trụ sở của nó được chuyển đến Berlin.[69] Ông được thăng chức SS-Obergruppenführer und General der Polizei vào ngày 24 tháng 9 năm 1941.[27]